package code_capriccio;

import java.util.*;


public class Demo13 {


//    public static void main(String[] args) {
//        String str = "a good   example";
//        String[] strs = str.split(" ");
//        for(String s : strs) {
//            System.out.println(s + "0");
//        }
//    }



    //   (数组篇)(数组篇)(数组篇)(数组篇)(数组篇)

    //704. 二分查找
    public int search(int[] nums, int target) {
        int mid = -1;;
        for(int left = 0, right = nums.length - 1; left <= right;) {
            mid = left + (right - left) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }



    //27. 移除元素
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0, right = n;   // left指向已遍历数组中非val值的最后一个元素
        for(int cur = 0; cur < right; ) {
            if(nums[cur] != val) {
                left++;
                cur++;
            }
            else swap(nums, cur, --right);
        }
        return left;
    }
    public void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }



    //977. 有序数组的平方
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1, pos = n;
        int[] ret = new int[n];
        while(left <= right) {
            if(Math.abs(nums[left]) >= Math.abs(nums[right])) {
                ret[--pos] = nums[left] * nums[left++];
            } else {
                ret[--pos] = nums[right] * nums[right--];
            }
        }
        return ret;
    }



    //LCR 008. 长度最小的子数组
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sum = 0,  ret = nums.length + 1;
        while(right < nums.length) {
            sum += nums[right];
            while(sum >= target) {
                ret = Math.min(ret, right - left + 1);
                sum -= nums[left++];
            }
            right++;
        }
        return ret == nums.length + 1 ? 0 : ret;
    }


    //59. 螺旋矩阵 II
    static int num = 1;
    public static int[][] generateMatrix(int n) {
        int[][] ret = new int[n][n];
        int i = 0;
        while(i < n / 2.0) {
            generate(ret, i++, n);
        }
        return ret;
    }
    public static void generate(int[][] nums, int pos, int n) {
        for(int j = pos; j < n - pos; j++) nums[pos][j] = num++;
        for(int i = pos + 1; i < n - pos; i++) nums[i][n - pos - 1] = num++;
        for(int j = n - pos - 2; j >= pos; j--) nums[n - pos - 1][j] = num++;
        for(int i = n - pos - 2; i > pos; i--) nums[i][pos] = num++;
    }




    // (哈希表篇)(哈希表篇)(哈希表篇)(哈希表篇)(哈希表篇)

    //LCR 032. 有效的字母异位词
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        int[] count = new int[26];
        boolean flag = false;
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) != t.charAt(i)) flag = true;
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for(int i = 0; i < 26; i++) if(count[i] != 0) return false;
        return true;
    }



    //349. 两个数组的交集
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] count = new int[1001];
        for(int x : nums1) count[x]++;
        Set<Integer> hash = new HashSet<>();
        for(int x : nums2) {
            if(count[x] != 0) hash.add(x);
        }

        int[] ret = new int[hash.size()];
        int k = 0;
        for(Integer x : hash) ret[k++] = x;
        return ret;
    }




    //202. 快乐数
    public boolean isHappy(int n) {
        Set<Integer> hash = new HashSet<>();
        hash.add(n);
        while(n != 1) {
            n = convert(n);
            if(hash.contains(n)) return false;
            hash.add(n);
        }
        return true;
    }
    private int convert(int n) {
        int sum = 0;
        while(n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }



    //1. 两数之和
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            if(hash.containsKey(x)) {
                return new int[]{i, hash.get(x)};
            }else {
                hash.put(nums[i], i);
            }
        }
        return null;
    }



    //





    //383. 赎金信
    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.length() > magazine.length()) return false;
        int[] count = new int[26];
        for(char ch : ransomNote.toCharArray()) count[ch - 'a']++;
        for(char ch : magazine.toCharArray()) count[ch - 'a']--;
        for(int x : count) if(x > 0) return false;
        return true;
    }



    //LCR 007. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        if(nums.length < 3) return ret;
        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 2; i++) {
            while(i > 0 && i < nums.length - 2 && nums[i] == nums[i - 1]) i++;
            if(i == nums.length - 2) break;
            int sum = -nums[i];
            for(int left = i + 1, right = nums.length - 1; left < right; ) {
                if(nums[left] + nums[right] == sum) {
                    ret.add(Arrays.asList(nums[i], nums[left++], nums[right--]));
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
                else if(nums[left] + nums[right] > sum) right--;
                else left++;
            }
        }
        return ret;
    }




    //18. 四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        if(nums.length < 4) return ret;
        Arrays.sort(nums);

        for(int i = 0; i < nums.length - 3; i++) {
            // 跳过已经重复过的 i 的情况
            while(i > 0 && i < nums.length - 3 && nums[i] == nums[i-1]) i++;
            if(i == nums.length - 3) break;
            int sum1 = target - nums[i];
            for(int j = i + 1; j < nums.length - 2; j++) {
                // 跳过已经重复过的 j 的情况
                while(j > i + 1 && j < nums.length-2 && nums[j] == nums[j-1]) j++;
                if(j == nums.length - 2) break;
                int left = j + 1, right = nums.length - 1;
                // 防止四数之和出现溢出的情况
                long sum2 = (long)sum1 - nums[j];
                while(left < right) {
                    if(nums[left] + nums[right] == sum2) {
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--]));
                        // 对 left和right 去重
                        while(left < right && nums[left] == nums[left - 1]) left++;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }
                    else if(nums[left] + nums[right] > sum2) right--;
                    else left++;
                }
            }
        }
        return ret;
    }




    // (字符串)(字符串)(字符串)(字符串)(字符串)(字符串)(字符串)(字符串)

    //344. 反转字符串
    public void reverseString(char[] s) {
        reverse(s, 0, s.length - 1);
    }
    public void reverse(char[] s, int left, int right) {
        while(left < right) {
            char tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }



    //541. 反转字符串 II
    public String reverseStr(String _s, int k) {
        char[] s = _s.toCharArray();
        int n = s.length;
        int left = 0, right = 0;
        while(right < n) {
            right += k;
            if(right < n) reverse(s, left, right - 1);
            else reverse(s, left, n - 1);
            left = right = right + k;
        }
        return new String(s);
    }
//    public void reverse(char[] s, int left, int right) {
//        while(left < right) {
//            char tmp = s[left];
//            s[left++] = s[right];
//            s[right--] = tmp;
//        }
//    }




    //LCR 181. 字符串中的单词反转
    public String reverseMessage(String message) {
        int n = message.length();
        char[] mes = message.toCharArray();
        char[] ret = new char[n];
        int k = 0, cur = n - 1;
        // 从后往前遍历添加单词，顺便将整条信息的单词逆序
        while(cur >= 0) {
            // 去除多余的空格
            while(cur >= 0 && mes[cur] == ' ') cur--;
            // 如果此时 ret 里面已有单词且添加空格
            if(cur >= 0 && k > 0) ret[k++] = ' ';
            // 将单词填充到 ret 数组中
            while(cur >= 0 && mes[cur] != ' ') ret[k++] = mes[cur--];
        }

        // 逐个逆序每个单词
        for(int left = 0, right = 0; right < k; ) {
            while(right < k && ret[right] != ' ') right++;
            reverse(ret, left, right - 1);
            left = right = right + 1;
        }
        return new String(ret, 0, k);
    }
//    public void reverse(char[] s, int left, int right) {
//        while(left < right) {
//            char tmp = s[left];
//            s[left++] = s[right];
//            s[right--] = tmp;
//        }
//    }



    //28. 找出字符串中第一个匹配项的下标
    public int strStr(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();
        if(m < n) return -1;
        for(int i = 0; i < m - n + 1; i++) {
            if(haystack.charAt(i) == needle.charAt(0)) {
                int j = i, k = 0;
                while(k < n && haystack.charAt(j) == needle.charAt(k)) {
                    j++; k++;
                }
                if(k == n) return i;
            }
        }
        return -1;
    }



    //459. 重复的子字符串
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for(int i = 1; i <= n / 2; i++) {
            if(n % i != 0) continue;
            String str = s.substring(0, i);
            boolean flag = true;
            for(int j = 0, k = 0; j < n; j++, k++) {
                if(k == str.length()) k = 0;
                if(s.charAt(j) != str.charAt(k)) {
                    flag = false;
                    break;
                }
            }
            if(flag) return true;
        }
        return false;
    }




    // 707. 设计链表
    class MyLinkedList {
        class ListNode {
            int val;
            ListNode next;
            public ListNode() {}
            public ListNode(int val) {
                this.val = val;
            }
        }
        private ListNode head, tail;
        private int len;

        public MyLinkedList() {
            head = tail = new ListNode();   // 带有头结点的链表
        }

        public int get(int index) {
            if (index < 0 || index >= len) return -1;
            if (index == len - 1) return tail.val;

            ListNode cur = head.next;
            while (index-- > 0) cur = cur.next;
            return cur.val;
        }

        public void addAtHead(int val) {
            ListNode node = new ListNode(val);
            node.next = head.next;
            head.next = node;
            len++;

            if (tail == head) tail = node;
        }

        public void addAtTail(int val) {
            ListNode node = new ListNode(val);
            tail.next = node;
            tail = node;
            len++;
        }

        public void addAtIndex(int index, int val) {
            if (index > len) return;
            if (index == len) {
                addAtTail(val);
                return;
            }

            ListNode prev = head, cur = head.next;
            while (index-- > 0) {
                prev = cur;
                cur = cur.next;
            }
            ListNode node = new ListNode(val);
            node.next = cur;
            prev.next = node;
            len++;
        }

        public void deleteAtIndex(int index) {
            if (index < 0 || index >= len) return;

            ListNode prev = head, cur = head.next;
            while (index-- > 0) {
                prev = cur;
                cur = cur.next;
            }
            prev.next = cur.next;
            if (cur.next == null) tail = prev;
            len--;
        }
    }


}
